#include <iostream>
using namespace std;

template<class T>
class Node {
public:
    Node *next;
    T data;
    Node(T data) {
        this->data = data;
        this->next = nullptr;
    }
};

template<class T>
class LinkedListStack {
public:
    LinkedListStack() {
        this->head = nullptr;
    }
    ~LinkedListStack() {
        Node<T> *t;
        while(head != nullptr) {
            t = head->next;
            delete head;
            head = t;
        }
    }
    // 入栈
    void push(T data) {
        // 栈内无元素
        if (head == nullptr) {
            head = new Node<T>(data);
            return;
        }
        
        Node<T> *t = new Node<T>(data);
        t->next = head;
        head = t;
    }
    // 判断栈是否为空
    bool is_empty() {
        return head == nullptr;
    }
    // 出栈
    void pop() {
        if (is_empty())
            throw "stack is empty";
        Node<T> *t = head->next;
        delete head;
        head = t;        
    }
    // 遍历
    void traverse() {
        Node<T> *t = head;
        while(t != nullptr) {
            cout << t->data << " ";
            t = t->next;
        }
        cout << endl;
    }
    // 返回栈顶元素
    T &top() {
        return &(head->data);
    }
private:
    Node<T> *head;
};